package com.caizhigang.dsag.binarysearch;

/**
 * 二分查找
 */
public class BinarySearch1 {



    static int[] nums = {1, 2, 3, 4, 5, 6,7};

    public static void main(String[] args) {
        binarsearch(nums, 7);

    }

    public static void binarsearch(int[] arrays, int numSearch) {
        int low = 0;
        int high = arrays.length-1;

        while (low <=high) {
            int middle = (low + high) >> 1;
            if (arrays[middle] > numSearch) {
                high = middle - 1;
            } else if (arrays[middle] < numSearch) {
                low = middle + 1;
            } else {
                System.out.println("查找数的下标是:"+middle);
                return;
            }
        }
        System.out.println("所查找数字不在数组中");
    }

/**
 * 二分法容易出错的地方
 * 1.循环退出条件注意是 low<=high,而不是 low<high
 * 2.mid 取值用右移 更高效   (low + high) >> 1。且不容易溢出
 * 3.low和 igh 更新   如果写成 low=middle 或high=middle  如果死循环
 *
 *
 * 二分查的局限性
 * 1.分查找依赖的是顺序表结构，简单点说就是数组。
 * 那二分查找能否依赖其他数据结构呢？比如链表。答案是不可以的，
 * 主要原因是二分查找算法需要按照下标随机访问元素。
 * 我们在数组和链表那两节讲过，
 * 数组按照下标随机访问数据的时间复杂度是 O(1)，
 * 而链表随机访问的时间复杂度是 O(n)。
 * 所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。
 *
 *
 * 2.二分查找针对的是有序数据。
 *   1.因此而适合静态数据。动态数据维护数据的有序性成本较高
 *   2.如果数据频繁的插入 删除 二叉树更合适
 *
 * 3.数据量太大也不适合二分查找
 *  (1) 数据量太小不明显.遍历即可
 *  (2) 例外：如果数据的大小比较耗时 。数据量大小都推荐二分 查找。减少比较次数也会有优势。
 *
 * 4.数据量太小不适合二分查找
 * (1) 数据量太小不明显.遍历即可
 * (2) 例外：如果数据的大小比较耗时 。数据量大小都推荐二分 查找。减少比较次数也会有优势。
 *
 */




}
